What is a recursive algorithm?
n! = 1•2•3...n and 0! = 1 (called initial case)
So the recursive defintiion n! = n•(n-1)!
Algorithm F(n)
if n = 0 then return 1 // base case
else F(n-1)•n // recursive call
Basic operation? multiplication during the recursive call
Formula for multiplication
M(n) = M(n-1) + 1
is a recursive formula too. This is typical.
We need the initial case which corresponds to the base case
M(0) = 0
There are no multiplications
Solve by the method of backward substitutions
M(n) = M(n-1) + 1
= [M(n-2) + 1] + 1 = M(n-2) + 2 substituted M(n-2) for M(n-1)
= [M(n-3) + 1] + 2 = M(n-3) + 3 substituted M(n-3) for M(n-2)
... a pattern evolves
= M(0) + n
= n
Not surprising!
Therefore M(n) ε Θ(n)
1. Specify problem size
2. Identify basic operation
3. Worst, best, average case
4. Write recursive relation for the number of basic operation. Don't forget the initial conditions (IC)
5. Solve recursive relation and order of growth
Stop here?
Explain the problem using figure
Demo and show recursion
1. Problem size is n, the number of discs
2. The basic operation is moving a disc from rod to another
3. There is no worst or best case
4. Recursive relation for moving n discs
M(n) = M(n-1) + 1 + M(n-1) = 2M(n-1) + 1
IC: M(1) = 1
5. Solve using backward substitution
M(n) = 2M(n-1) + 1
= 2[2M(n-2) + 1] +1 = 22M(n-2) + 2+1
=22[2M(n-3) +1] + 2+1 = 23M(n-3) + 22 + 2 + 1
...
M(n) = 2iM(n-i) + ∑j=0-i2j = 2iM(n-i) + 2i-1
...
M(n) = 2n-1M(n-(n-1)) + 2n-1-1 = 2n-1M(1) + 2n-1-1 = 2n-1 + 2n-1-1 = 2n-1
M(n) ε Θ(2n)
Terrible. Can we do it better?
Where did the exponential term come from? Because two recursive calls are made. Suppose three recursive calls are made, what is the order of growth.
Lesson learned: Be careful of the recursive algorithm, they can grow exponential.
Especial if the problem size is measured by the level of the recursive tree and the operation count is total number of nodes.
Algorithm BinRec(n)
if n = 1 then return 1
else return BinRec(floor(n/2)) + 1
1. Problem size is n
2. Basic operation is the addition in the recursive call
3. There is no difference between worst and best case
4. Recursive relation including initial conditions
A(n) = A(floor(n/2)) + 1
IC A(1) = 0
5. Solve recursive relation
The division and floor function in the argument of the recursive call makes the analysis difficult.
We could make the variable substitution, n = 2k, could get rid of the definition,
but the substitution skips a lot of values for n.
The smoothness rule (see appendix B) says that is ok.
Smoothness rule
T(n) eventually non-decreasing and f(n) be smooth {eventually non-decreasing and f(2n) ε Θ(f(n))}
if T(n) ε Θ(f(n)) for n powers of b then T(n) ε Θ(f(n)) for all n.
Works for O and Ω.
substitute n = 2k (also k = lg(n))
A(2k) = A(2k-1) + 1 and IC A(20) = 0
A(2k) = [A(2k-2) + 1] + 1 = A(2k-2) + 2
= [A(2k-3) + 1] + 2 = A(2k-3) + 3
...
= A(2k-i) + i
...
= A(2k-k) + k
A(2k) = k
Substitute back k = lg(n)
A(n) = lg(n) ε Θ(lg n)
A classic example for more elaborate recursion relations.
Fibonacci Sequence: 0, 1, 1 2, 3, 5, 8, 13, 21, 34, ...
Fibonacci (1202) proposed for the growth of rabbits
Can be defined by the simple recurrence
F(n) = F(n-1) + F(n-2) for n > 1
IC: F(0) = 0 and F(1) = 1 (why do we need two ICs)
ax(n) + bx(n-1) + cx(n-2) = 0
Homogenous because the recurrence equals zero.
Why second-order linear? Substitute the proposed solution x(n) = rn
a rn + b rn-1 + c rn-2 = 0
divide by rn
a + b r + c r2 = 0, characteristic equation is a second order polynomial.
The real roots are solutions
x(n) = αr1n + βr2n
α and β are determined from the
Apply to Fibonacci Recursion
F(n) - F(n-1) - F(n-2) = 0, homogenous second order with constant coefficients
r2 - r - 1 = 0, characteristic equation
r1,2 = (1 ± √5)/2 = φ or φ' { φ = (1+√5)/2 and φ' = (1-√5)/2}
The general form of the solution
F(n) = αφn + βφ' n where α and β are unknows
Using the ICs
α + β = 0
φα + φ'β = 1
Solve by substituting the first equation into the second, get α = 1/√5 and β = -1/√5
So
F(n) = 1/√5 (φn - φ' n) = φn/√5 rounded to the nearest integer
Algorithm F(n)
if n ≤ 1 then return n
else return F(n-1) + F(n-2)
1. Problem size is n, the sequence number for the Fibonacci number
2. Basic operation is the sum in recursive call
3. No difference between worst and best case
4. Recurrence relation
A(n) = A(n-1) + A(n-2) + 1
IC: A(0) = A(1) = 0
or
A(n) - A(n-1) - A(n-2) = 1, Inhomogeneous recurrences because of the 1
In general solution to the inhomogeneous problem is equal to the sum of solution to homogenous problem plus solution only to the inhomogeneous part. The undetermined coefficients of the solution for the homogenous problem are used to satisfy the IC.
In this case A(n) = B(n) + I(n) where
A(n) is solution to complete inhomogeneous problem
B(n) is solution to homogeneous problem
I(n) solution to only the inhomogeneous part of the problem
We guess at I(n) and then determine the new IC for the homogenous problem for B(n)
For this problem the correct guess is I(n) = 1
substitute A(n) = B(n) -1 into the recursion and get
B(n) - B(n-1) - B(n-2) = 0 with IC B(0) = B(1) = 1
The same as the relation for F(n) with different IC
We do not really need the exact solution; We can conclude
A(n) = B(n) -1 = F(n+1) - 1 ε Θ(φn), exponential
There is the Master Theorem that give the asymptotic limit for many common problems.
Algorithm Fib(n)
F[1] ← 0; F[1] ← 1
for i ← 2 to n do
F[i] ← F[i-1] + F[i-2]
return F[n]
Order of growth is Θ(n).
Why is it so much better then the recursive algorithm? Draw the recursive tree.